package 栈;

import java.util.Stack;

/**
 * @author 翟晓龙
 * @date 2022/4/27
 */
public class 两个栈实现队列 {

    /**
     *
     */
    class CQueue {

        Stack<Integer> stack1=new Stack<>();
        Stack<Integer>stack2=new Stack<>();
        public CQueue() {
        }
        public void appendTail(int value) {
            stack1.push(value);
        }

        /**
         * 一个栈stack1用作数据存储，插入尾时候直接插入stack1，
         * 而删除头的时候将数据先加入到另一个栈stack2中，返回并删除栈顶元素，
         * 将stack2顺序加入stack1中实现一个复原，但是这样操作插入时间复杂度为O(1),删除时间复杂度为O(n)比较高。
         * @return
         */
        public int deleteHead() {
            if(stack1.isEmpty())
                return -1;

            while (!stack1.isEmpty())
            {
                stack2.push(stack1.pop());
            }
            int value= stack2.pop();
            while (!stack2.isEmpty())
            {
                stack1.push(stack2.pop());
            }
            return  value;
        }

        /**
         * 用stack1作插入，stack2作删除
         * @return
         */
        public int deleteHead2() {
            // 如果第二个栈为空 将stack1数据加入stack2
            if (stack2.isEmpty()) {
                while (!stack1.isEmpty()) {
                    stack2.push(stack1.pop());
                }
            } //如果stack2依然为空 说明没有数据
            if (stack2.isEmpty()) {
                return -1;
            } else {//否则删除
                int deleteItem = stack2.pop();
                return deleteItem;
            }
        }
    }
}
